﻿public class Solution {
    public int FindTargetSumWays(int[] nums, int target)
    {
        int sum = nums.Sum();
        if ((sum + target) % 2 != 0 || sum < Math.Abs(target)) return 0;

        int N = (sum + target) / 2;
        int[] dp = new int[N+1];
        dp[0] = 1;
        
        for (int i = 0; i < nums.Length; i++)
        {
            for (int j = N; j >= nums[i]; j--)
            {
                dp[j] += dp[j - nums[i]];
            }
        }
        return dp[N];
    }

    public static void Main(string[] args)
    {
        int[] nums = [1, 1, 1, 1, 1];
        int target = 3;
        Solution solution = new Solution();
        int res = solution.FindTargetSumWays(nums, target);
        Console.WriteLine(res);
    }
}